Vợ đầu của Goleniewski là người Nga có tên Anna Malinovskaya nhũ danh Dyachenko sinh năm 1926.[41] Trong chiến tranh Xô–Đức, bà bị bắt lao động cưỡng bức tại Đức. Bà từng cưới một người Ba Lan ở Nowy Tomysl[38] và sinh con gái Halina năm 1944. Sau khi chồng qua đời, Anna tái hôn với Michał. Họ có một con gái Danuta năm 1946 và một con trai Jerzy Goleniewski năm 1950.[41] Về sau Jerzy chơi bass cho ban nhạc Breakout[16] và mất năm 1989.[42] Từ thập niên 1950, Anna bị bệnh tâm thần nghiêm trọng, cấp trên của Goleniewski là Stefan Antosiewicz nhận định có thể do sang chấn khủng khiếp thời chiến.[41] Goleniewski không chịu nổi cuộc sống gia đình.[16] Ông thường báo cáo bệnh tình nghiêm trọng của vợ lên cho cấp trên. Mọi nỗ lực chữa trị đều không có kết quả dẫn đến Anna bị chẩn đoán mắc chứng hoang tưởng phân liệt.[43] Theo lời bác sĩ khuyên, Goleniewski chuyển đến nhà mẹ đẻ,[41] dù nói rằng do bị vợ đuổi ra khỏi nhà. Trở lại tháng 1 năm 1957, Anna quyết định đưa con gái Halina về Liên Xô để lấy lại quốc tịch cũ.[44] Goleniewski nói họ chưa bao giờ chính thức ly hôn.[45]

Trong chuyến công tác tháng 7 năm 1957, Goleniewski gặp Irmgard Margareta Kampf người Đức tại Đông Berlin.[41] Margareta sinh ngày 6 tháng 1 năm 1929 tại Berlin,[42] từng làm thư ký tại trường trung học số 13 Berlin (tiếng Đức: Oberschule No. 13)[46] và chăm sóc cha mẹ đã nghỉ hưu.[41] (Báo Gazeta Wyborcza gọi bà là "Inga Kampf").[47] Goleniewski tự giới thiệu bản thân là nhà báo Ba Lan Roman Jan chuyên cộng tác làm các ấn phẩm của CHDC Đức.[48] Đồng thời, ông nói với Margareta rằng mình từng bị kết tội tham gia kháng chiến và cả gia đình (trừ mẹ) bị Đức quốc xã giết hại.[49] Trong thời gian dài, Goleniewski không báo cáo cấp trên về quan hệ với Irmgard.[48] Nửa đầu năm 1959, Tổng cục phó Đại tá Henryk Sokolak nhận thấy Goleniewski năng đến CHDC Đức hơn bình thường. Tháng 3 năm 1960, Sokolak tiến hành kiểm tra thực địa nhưng không phát hiện ra điều gì khả nghi.[50] Trong khi ấy, Goleniewski lừa dối Irmgard khi có quan hệ với một phụ nữ khác khác tại Warszawa. Tháng 9 năm 1960, Bộ Nội vụ phát hiện Goleniewski gặp gỡ Kampf, thẩm vấn bà rồi cấm Goleniewski tạm thời không được xuất ngoại. Goleniewski bị sốc tinh thần, cấp dưới là trung úy Jan Bisztyga nhận thấy điều này đồng thời nói ông "nghiện" ma túy trong thời gian dài.[51]

Tháng 10 năm 1960, Goleniewski liên hệ với luật sư để cố gắng ly dị và kết hôn với người tình mới. Tháng 11, Goleniewski nộp bản giải trình dài 9 trang lên Tổng cục 1, trong đó ghi quen biết Imgard từ năm 1958 (sự thật là năm 1957), ông bị lay động và cảm kích trước nhiệt huyết tận tâm của bà đối với hệ thống chính quyền CHDC Đức,[52] coi đó là điểm thu hút nhất đối với cá nhân, đồng thời bày tỏ ý định muốn cưới bà.[53] Tuy nhiên, vì việc ly dị phức tạp về mặt pháp lý và Goleniewski lại đang là người nhà nước,[16] kể cả Irmgard là người Đông Đức cùng phe XHCN, Tổng cục 1 không bỏ lệnh cấm Goleniewski xuất ngoại để tiếp tục gặp gỡ người tình.[54] Goleniewski nỗ lực để dỡ bỏ được lệnh cấm này bằng bất cứ giá nào, dù nếu thất bại thì có nguy cơ bị sa thải. Bộ trưởng Nội vụ Władysław Wicha xem xét xử lý vấn đề này của Tổng cục 1. Ngày 22 tháng 12, Goleniewski xin phép Witold Sienkiewicz đi công tác Berlin từ ngày 26 tháng 12 năm 1960 đến ngày 3 tháng 1 năm 1961 để giải thích và nói lời chia tay với Irmgard. Phó bộ trưởng Nội vụ Mieczysław Moczar phụ trách giám sát tình báo đã gặp và phê chuẩn chuyến đi này cho Goleniewski,[55] ngày quay lại được gia thêm đến 8 tháng 1.[56]